6.6.1 Stacks


What's a Stack?

	a List restricted to add/remove only at top
	only the top item on the stack is accessible
	LIFO (last in first out)
	items come out in reverse order


What are some examples where Stacks are used?

	stack of plates
	method calls
	reversing lists


What are the operations on a Stack?

	push
	pop
	top
	all are constant time


Stack Interface

public interface Stack {
	void push(Object x);
	Object pop();
	Object top();
	boolean isEmpty();
}


How does Stack fit into the Java Collections hierarchy?

	java.util.Stack extends Vector (slow)
	better to use addFirst, removeFirst, getFirst on LinkedList


What kinds of applications is a Stack good for?
What kinds of problems can be solved using a Stack?

	useful when you need to process data in reverse order



11.1 Balanced Symbol Checker

What's a Balanced Symbol Checker?

	missing brackets ( ), ], } ) often cause compilers
	    to print many unrelated error messages

	a balanced symbol checker finds these problems

	assume the program ignores all symbols except brackets


Balanced Symbol Checker Algorithm

	(1) make an empty stack
	(2) for each opening symbol, push it on the stack
	(3) for each closing symbol, compare it with the top of stack
	   (a) if the stack is empty, report error
	   (b) if the symbols don't match, report error
	(4) if stack is not empty at the end of file, report error


DEMO	(Balanced.java)



11.2 Simple Calculator


Why is this called an infix expression?

	1 + 2 - 3 * 4 / 5


What's the algorithm for evaluating infix expressions?

	(1) precedence (* and / have higher precedence than + and -)
	(2) associativity (all of these operators associate left-to-right)


Can you write the expression so that precedence and associativity
rules are not needed?

	(1) always fully parenthesize expressions (worse than rules?)
	(2) use Postfix notation


Convert the expression to postfix.

	1 + 2 - 3 * 4 / 5

	1 2 + 3 4 * 5 / -


11.2.1 Postfix Evaluation

What's the algorithm for evaluating Postfix expressions?

	(1) make an empty stack
	(2) Scan the expression left-to-right
	(3) If the symbol is an operand, push it on the stack
	(4) If the symbol is an operator
	    (a) pop the top two values off the stack
	    (b) perform the operator 
		(first popped is right operand, second is left)
	    (c) push the result on the stack
	    (d) if the stack has less than two values, report error
	(5) After reading the expression, the answer is on the stack
	    (a) if the stack has more or less than one value, error


Evaluate the postfix expression using a Stack.

	1 2 + 3 4 * 5 / -


DEMO	(Postfix evaluator)



11.2.2 Infix to Postfix Conversion


How can you use the postfix evaluator to evaluate infix expressions?

	convert infix to postfix
	use postfix evaluator


What's the algorithm for converting Infix to Postfix?

	(1) Create a stack for storing operators
	(2) Initialize the Postfix expression to the empty string
	(3) Scan the Infix expression from left-to-right
	(4) If the symbol is an operand
	    append it to the Postfix expression
	(5) If the symbol is an operator
	    a. while the operator on the stack has precedence >=
	       pop the operator and append it to the Postfix expression
	    b. push the new operator onto the stack
	(6) If the symbol is a left paren
	    push the left paren on the stack
	(7) If the symbol is a right paren
	    pop the stack and append to output until left paren
	(8) If at the end of the Infix expression
	    pop operators left on the stack and append to output


Convert the expression to postfix using the algorithm.

	1 + 2 - 3 * 4 / 5


DEMO	(Infix to Postfix)